#include<bits/stdc++.h>
using namespace std;

inline int read() {
	int x = 0, f = 0; char ch = getchar();
	while(ch < '0' or ch > '9') f |= (ch == '-'), ch = getchar();
	while(ch >= '0' and ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}
int __stk[128], __top;
inline void write(int x) {
    if(x < 0) putchar('-'), x = -x;
	do { __stk[++__top] = x % 10, x /= 10; } while(x);
	while (__top) putchar(__stk[__top--] + '0');
}
bool stmer;
const int N = 1e5 + 10, mod = 1e9 + 7;
void add(int &x, int y) { (x += y) >= mod and (x -= mod); }
void mul(int &x, int y) { x = x * y % mod; }
struct node {
    int to, x;
    node operator + (const node &p) const {
        return {p.to, (x + p.x) % mod};
    }
} p[N][2], tmp[N];
int n, m, T;
int nex[N];
char s[N];
void solve() {
    int fail = 0;
    p[0][s[1] - '0'] = {1, 0};
    if(m == 1) p[0][s[1] - '0'] = {0, 1};
    p[0][(s[1] - '0') ^ 1] = {0, 0};
    for(int i = 1; i < m; i++) {
        int op = s[i + 1] - '0';
        p[i][op] = {i + 1, 0};
        p[i][!op] = p[fail][!op];
        fail = p[fail][op].to;
        if(i + 1 == m) p[i][op] = {fail, 1};
    }
    for(int i = 3; i <= n; i++) {
        for(int j = 0; j < m; j++) tmp[j] = p[j][1] + p[p[j][1].to][0];
        for(int j = 0; j < m; j++) swap(tmp[j], p[j][1]), swap(tmp[j], p[j][0]);
        // cout << p[0][1].to << " " << p[0][1].x << '\n';
    }
    if(n == 1) write(p[0][0].x);
    else write(p[0][1].x); putchar('\n');
}
bool edmer;
signed main() {
	freopen("brotherhood.in", "r", stdin);
	freopen("brotherhood.ans", "w", stdout);
	// cerr << "[Memory] " << (&stmer - &edmer) / 1024 / 1024 << " MB\n";
    n = read(), T = read();
    for(int i = 1; i <= T; i++) {
        scanf("%s", s + 1), m = strlen(s + 1);
        solve();
    }
    // cerr << "[Runtime] " << (double) clock() / CLOCKS_PER_SEC << " seconds";
	return 0;
} 